"""
because time complexity，use quick or incorporate into sort,

quick sort need double point, is not suitability

so, we use incorporate into method

need a func, find link list middle node, separate link list, use fast and slow point

"""


class LinkNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    def show(self):
        tmp = self
        res = []
        while tmp:
            if tmp.next:
                res.append(str(tmp.val))
                tmp = tmp.next
            else:
                res.append(str(tmp.val))
                tmp = None
        print('->'.join(res))


def git_mid(head):
    slow = fast = head
    if head is None:
        return slow
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def merge(l, r):
    # l first sub link list head point
    # r second sub link list head point
    # a: instance a 0 LinkNode, for point merge link list head
    # q: init equal a, for merge link list, record is operate current node
    a = LinkNode(0)
    q = a
    while l and r:
        if l.val > r.val:
            q.next = r
            r = r.next
        else:
            q.next = l
            l = l.next
        q = q.next
    if l:
        q.next = l
    if r:
        q.next = r
    return a.next


def sort_list(head):
    if head is None or head.next is None:
        return head
    mid = git_mid(head)
    l = head
    r = mid.next
    mid.next = None
    return merge(sort_list(l), sort_list(r))


l1 = LinkNode(1)
l2 = LinkNode(2)
l3 = LinkNode(3)
l4 = LinkNode(4)
l4.next = l2
l2.next = l1
l1.next = l3
result = sort_list(l4)
result.show()
